package org.example.algorithm.dynamicProgramming;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @Description: 动态规划
 */

public class TestDynamicProgramming {

    public static void main(String[] args) {
//        List<List<Integer>> generate = generate(5);
//        System.out.println(generate);
//        System.out.println(getRow(3));
//        System.out.println(tribonacci(25));
//
//        System.out.println(jump(new int[]{2, 3, 1, 1, 4}));
//        System.out.println(wateringPlants(new int[]{2, 2, 3, 3}, 5));
//        System.out.println(minimumRefill(new int[]{2, 2, 3, 3}, 3, 4));
//        System.out.println(countTestedDevices(new int[]{1, 1, 2, 1, 3}));garbageCollection
//        System.out.println(garbageCollection(new String[]{"G", "P", "GP", "GG"}, new int[]{2, 4, 3}));
//        System.out.println(minimumRounds(new int[]{2, 2, 3, 3, 2, 4, 4, 4, 4, 4}));
//        System.out.println(deleteAndEarn(new int[]{2, 2, 3, 3, 3, 4}));
//        System.out.println(uniquePaths(3, 7));
//        System.out.println(maxProfitAssignment(new int[]{2, 4, 6, 8, 10}, new int[]{10, 20, 30, 40, 50}, new int[]{4, 5, 6, 7}));
        System.out.println(findWinners(new int[][]{{1, 3}, {2, 3}, {3, 6}, {5, 6}, {5, 7}, {4, 5}, {4, 8}, {4, 9}, {10, 4}, {10, 9}}));
    }

    /**
     * LeetCode：118 杨辉三角
     *
     * @param numRows
     * @return
     */
    static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> dp = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> rows = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    rows.add(1);
                    continue;
                }
                rows.add(dp.get(i - 1).get(j - 1) + dp.get(i - 1).get(j));
            }
            dp.add(rows);
        }
        return dp;
    }

    /**
     * LeetCode：119 杨辉三角 II
     *
     * @param rowIndex
     * @return
     */
    static List<Integer> getRow(int rowIndex) {
        List<List<Integer>> dp = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {
            List<Integer> rows = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    rows.add(1);
                    continue;
                }
                rows.add(dp.get(i - 1).get(j - 1) + dp.get(i - 1).get(j));
            }
            dp.add(rows);
        }
        return dp.get(rowIndex);
    }

    /**
     * LeetCode：1137 第 N 个泰波那契数
     *
     * @param n
     * @return
     */
    static int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        return dp[n];
    }

    /**
     * 跳跃游戏 II
     * 定义状态、设置初始状态、确定状态转移方程
     * nums = [2,3,1,1,4]
     * 定义状态
     * 当 nums[0] = 2 时，可以向后走最多2步
     *
     * @param nums
     * @return
     */
    static int jump(int[] nums) {
        int[] dp = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = nums.length;
        }
        dp[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] + j >= i) {
                    // 说明从j出发能走到i
                    dp[i] = Math.min(dp[j] + 1, dp[i]);
                }
            }
        }
        return dp[nums.length - 1];
    }


    /**
     * LeetCode 2079 给植物浇水
     *
     * @param plants
     * @param capacity
     * @return
     */
    static int wateringPlants(int[] plants, int capacity) {
        int n = plants.length;
        if (n == 1) {
            return 1;
        }
        // dp[i] ：给编号为 i 的植物浇水需要走的步数
        int[] dp = new int[plants.length];
        dp[0] = 1;
        // 桶内剩余的水
        int remain = capacity - plants[0];
        for (int i = 1; i < n; i++) {
            if (remain >= plants[i]) {
                // 可以浇水，不用返回
                dp[i] = dp[i - 1] + 1;
                // 重新计算桶内剩余的水
                remain = remain - plants[i];
            } else {
                // 2 * i 是取水的回到 i-1 的步数，需要返回
                dp[i] = dp[i - 1] + 1 + 2 * i;
                // 重新计算桶内剩余的水
                remain = capacity - plants[i];
            }
        }
        return dp[n - 1];
    }

    /**
     * LeetCode 2105 给植物浇水II
     *
     * @param plants
     * @param capacityA
     * @param capacityB
     * @return
     */
    static int minimumRefill(int[] plants, int capacityA, int capacityB) {
        int n = plants.length;
        if (n == 1 || n == 2) {
            return 0;
        }
        // dp[i] ：给编号为 i 的植物浇水的往返次数 0<=i<n/2
        int[] dp = new int[n / 2];
        dp[0] = 0;
        // A 桶内剩余的水
        int remainA = capacityA - plants[0];
        // B 桶内剩余的水
        int remainB = capacityB - plants[n - 1];
        for (int i = 1; i < n / 2; i++) {
            int comeAndGo = 0;
            if (remainA >= plants[i]) {
                // 重新计算A桶内剩余的水
                remainA = remainA - plants[i];
            } else {
                // 重新计算A桶内剩余的水
                remainA = capacityA - plants[i];
                comeAndGo++;
            }
            if (remainB >= plants[n - i - 1]) {
                // 重新计算B桶内剩余的水
                remainB = remainB - plants[n - i - 1];
            } else {
                // 重新计算B桶内剩余的水
                remainB = capacityB - plants[n - i - 1];
                comeAndGo++;
            }
            dp[i] = dp[i - 1] + comeAndGo;
        }
        if (n % 2 != 0 && Math.max(remainA, remainB) < plants[n / 2]) {
            return dp[n / 2 - 1] + 1;
        }
        return dp[n / 2 - 1];
    }


    /**
     * LeetCode 2960 统计已测试设备
     *
     * @param batteryPercentages
     * @return
     */
    static int countTestedDevices(int[] batteryPercentages) {
        int n = batteryPercentages.length;
        // dp[i] 表示 测试到下标为 i 的已测试设备数量
        int dp[] = new int[n];
        dp[0] = batteryPercentages[0] > 0 ? 1 : 0;
        for (int i = 1; i < n; i++) {
            dp[i] = batteryPercentages[i] - dp[i - 1] > 0 ? dp[i - 1] + 1 : dp[i - 1];
        }
        return dp[n - 1];
    }

    /**
     * LeetCode 2391. 收集垃圾的最少总时间
     *
     * @param garbage
     * @param travel
     * @return
     */
    static int garbageCollection(String[] garbage, int[] travel) {
        int n = garbage.length;
        int ans = garbage[0].length();
        int lastP = 0;
        int lastG = 0;
        int lastM = 0;
        // 找到每个垃圾车的最终的位置
        for (int i = n - 1; i > 0; i--) {
            if (garbage[i].contains("G")) {
                lastG = i;
                break;
            }

        }
        for (int i = n - 1; i > 0; i--) {
            if (garbage[i].contains("M")) {
                lastM = i;
                break;
            }
        }
        for (int i = n - 1; i > 0; i--) {
            if (garbage[i].contains("P")) {
                lastP = i;
                break;
            }
        }
        for (int i = 1; i < n; i++) {
            // 统计开车时间
            if (i <= lastG) {
                ans += travel[i - 1];
            }
            if (i <= lastM) {
                ans += travel[i - 1];
            }
            if (i <= lastP) {
                ans += travel[i - 1];
            }
            // 统计垃圾处理时间
            if (garbage[i].contains("G")) {
                int countG = garbage[i].length() - garbage[i].replace("G", "").length();
                ans += countG;
            }
            if (garbage[i].contains("M")) {
                int countM = garbage[i].length() - garbage[i].replace("M", "").length();
                ans += countM;
            }
            if (garbage[i].contains("P")) {
                int countP = garbage[i].length() - garbage[i].replace("P", "").length();
                ans += countP;
            }
        }
        return ans;
    }

    /**
     * LeetCode 2244. 完成任务需要的最小轮数
     *
     * @param tasks
     * @return
     */
    static int minimumRounds(int[] tasks) {
        if (tasks.length == 1) {
            return -1;
        }
        HashMap<Integer, Integer> taskMap = new HashMap<>();
        for (int task : tasks) {
            taskMap.put(task, taskMap.getOrDefault(task, 0) + 1);
        }
        if (taskMap.values().contains(1)) {
            return -1;
        }
        int ans = 0;
        for (Integer value : taskMap.values()) {
//            if (value % 3 == 0) {
//                ans += value / 3;
//            } else {
//                ans += value / 3 + 1;
//            }
            ans += (value + 2) / 3;
        }
        return ans;
    }


    /**
     * LeetCode 740 删除并获取点数
     *
     * @param nums
     * @return
     */
    static int deleteAndEarn(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int max = 0;
        for (int num : nums) {
            max = Math.max(max, num);
        }
        int[] sum = new int[max + 1];
        for (int num : nums) {
            sum[num] += num;
        }
        // nums[2,2,3,3,3,4] -> sums[0, 0, 4, 9, 4]
        // 计算 sums 能获取的最多的点数, 选了中间就不能选两边
        int[] dp = new int[max + 1];
        dp[0] = 0;
        dp[1] = sum[1];
        for (int i = 2; i <= max; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + sum[i]);
        }
        return dp[max];
    }


    /**
     * LeetCode 62 不同路径
     *
     * @param m
     * @param n
     * @return
     */
    static int uniquePaths(int m, int n) {
        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < m; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n - 1][m - 1];
    }

    /**
     * LeetCode 1953 可以工作的最大周数
     *
     * @param milestones
     * @return
     */
    static long numberOfWeeks(int[] milestones) {
        long max = 0;
        long result = 0;

        for (int milestone : milestones) {
            max = Math.max(max, milestone);
            result += milestone;
        }

        result -= max;

        if (max > result + 1) {
            return result * 2 + 1;
        } else {
            return result + max;
        }
    }

    /**
     * LeetCode 826 安排工作以达到最大收益
     *
     * @param difficulty
     * @param profit
     * @param worker
     * @return
     */
    static int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int result = 0;
        for (int i = 0; i < worker.length; i++) {
            int max = 0;
            for (int j = 0; j < difficulty.length; j++) {
                if (worker[i] >= difficulty[j]) {
                    max = Math.max(max, profit[j]);
                }
            }
            result += max;
        }
        return result;
    }

    /**
     * LeetCode 2225 找出输掉零场或一场比赛的玩家
     *
     * @param matches
     * @return
     */
    static List<List<Integer>> findWinners(int[][] matches) {
        int max = 0;
        for (int i = 0; i < matches.length; i++) {
            max = Math.max(matches[i][0], Math.max(matches[i][1], max));
        }
        int[] winners = new int[max + 1];
        int[] losers = new int[max + 1];
        for (int i = 0; i < matches.length; i++) {
            winners[matches[i][0]]++;
            losers[matches[i][1]]++;
        }
        List<Integer> winAll = new ArrayList<>(max);
        List<Integer> loseOne = new ArrayList<>(max);
        for (int i = 1; i <= max; i++) {
            if (winners[i] != 0 && losers[i] == 0) {
                winAll.add(i);
                continue;
            }
            if (losers[i] == 1) {
                loseOne.add(i);
            }
        }
        List<List<Integer>> result = new ArrayList<>(2);
        result.add(winAll);
        result.add(loseOne);
        return result;
    }

    /**
     * LeetCode 2028 找出缺失的观测数据
     */
    static int[] missingRolls(int[] rolls, int mean, int n) {
        int sum = 0;
        for (int roll : rolls) {
            sum += roll;
        }
        int total = (rolls.length + n) * mean;
        int sum1 = total - sum;
        int avg = sum1 / n;
        int mod = sum1 % n;
        if (sum1 < n || sum1 > 6 * n) {
            return new int[0];
        }
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            if (mod > 0) {
                if (mod + avg > 6) {
                    result[i] = 6;
                    mod -= 6 - avg;
                } else {
                    result[i] = mod + avg;
                    mod = 0;
                }
            } else {
                result[i] = avg;
            }
        }
        return result;
    }

}
